<?php
/**
 * User: helloJiu
 * Date: 2021/11/5
 * Time: 17:06
 */

namespace App\Algorithm\DP;


class NumSquares
{
    /**
     * @param Integer $n
     * @return Integer
     */
    function numSquares($n)
    {
        /*
            给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

            给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

            完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

             

            示例 1：

            输入：n = 12
            输出：3
            解释：12 = 4 + 4 + 4

            来源：力扣（LeetCode）
            链接：https://leetcode-cn.com/problems/perfect-squares
            著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
         */
        // $dp[$i]: 凑够$i需要的最小数量
        $dp = [];
        $nums = [];
        $j = 1;
        while (true) {
            $square = $j * $j;
            if ($square > $n) {
                break;
            }
            $nums[] = $square;
            $j++;
        }

        for ($i = 0; $i <= $n; $i++) {
            $dp[$i] = PHP_INT_MAX;
        }

        $dp[0] = 0;
        foreach ($nums as $num) {
            for ($i = 1; $i <= $n; $i++) {
                if ($i >= $num) {
                    $dp[$i] = min($dp[$i], $dp[$i - $num] + 1);
                }
            }
        }

        return $dp[$n] == PHP_INT_MAX ? -1 : $dp[$n];

    }
}